using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

using Flood.Extensions;

namespace Flood.FloodStrategies
{
	public sealed class FloodAdjacentColorSelectedGenetically : IFloodStrategy
	{
		private readonly int MaxGenerationsWithoutImprovment;
		private readonly int MaxPopulationSize;
		private readonly PuzzleConstants puzzleConstants;

		public FloodAdjacentColorSelectedGenetically(PuzzleConstants puzzleConstants, int maxGenerationsWithoutImprovement,
		                                             int maxPopulationSize)
		{
			MaxGenerationsWithoutImprovment = maxGenerationsWithoutImprovement;
			MaxPopulationSize = maxPopulationSize;
			this.puzzleConstants = puzzleConstants;
		}

		#region IFloodStrategy Members

		public Result GetNextToFlood(IEnumerable<Shape> moistShapes, Grid grid)
		{
			HashSet<string> variantsFlooded = new HashSet<string>();
			HashSet<string> variantsPermuted = new HashSet<string>();
			Dictionary<string, Permutation> population = BuildInitialPopulation(grid);

			Permutation bestSolution = population.OrderBy(kvp => kvp.Key.Length).First().Value;

			int generationsWithoutImprovement = 0;
			while (generationsWithoutImprovement < MaxGenerationsWithoutImprovment)
			{
				Dictionary<string, Permutation> evaluatedPopulation = new Dictionary<string, Permutation>();
				Permutation newBestSolution = EvaluateEachIndividualInThePopulation(
					grid,
					population,
					evaluatedPopulation,
					variantsFlooded,
					bestSolution);
				if (newBestSolution.Steps.Count < bestSolution.Steps.Count)
				{
					WriteOutput("-          was: " + bestSolution.Key + " " + bestSolution.Source);
					WriteOutput("- found better: " + newBestSolution.Key + " " + newBestSolution.Source);
					bestSolution = newBestSolution;

					generationsWithoutImprovement = 0;
				}
				else
				{
					generationsWithoutImprovement++;
				}
				population = CreateNextPopulation(variantsFlooded, variantsPermuted, evaluatedPopulation, bestSolution.Steps.Count);
				if (population.Count == 0)
				{
					break;
				}
			}
			return new Result(bestSolution.Steps, true);
		}

		#endregion

		[Conditional("DEBUG")]
		[Conditional("DETAILED")]
		[Conditional("MINIMAL")]
		private static void WriteOutput(string message)
		{
			Console.WriteLine(message);
		}

		private Dictionary<string, Permutation> CreateNextPopulation(ICollection<string> variantsFlooded, HashSet<string> variantsPermuted, ICollection<KeyValuePair<string, Permutation>> checkedPopulation, int bestSolutionLength)
		{
			IEnumerable<KeyValuePair<string, Permutation>> parentPopulation = GetParentPopulation(checkedPopulation,
			                                                                                      variantsFlooded,
			                                                                                      variantsPermuted,
			                                                                                      bestSolutionLength);

			Dictionary<string, Permutation> nextPopulation = new Dictionary<string, Permutation>();
			List<KeyValuePair<string, Permutation>> population = parentPopulation.Take(MaxPopulationSize).ToList();
			AddRemovalPermutations(nextPopulation, population, variantsFlooded);
			AddSwapPermutations(nextPopulation, population, variantsFlooded);
			return nextPopulation;
		}

		private IEnumerable<KeyValuePair<string, Permutation>> GetParentPopulation(ICollection<KeyValuePair<string, Permutation>> checkedPopulation, IEnumerable<string> variantsFlooded, HashSet<string> variantsPermuted, int bestSolutionLength)
		{
			if (checkedPopulation.Count < MaxPopulationSize)
			{
				foreach (var kvp in checkedPopulation)
				{
					if (variantsPermuted.Add(kvp.Key))
					{
						yield return kvp;
					}
				}
			}
			else
			{
				IOrderedEnumerable<KeyValuePair<string, Permutation>> orderedEnumerable =
					checkedPopulation
						.Where(kvp => kvp.Key.Length <= puzzleConstants.MaxFloods)
						.OrderBy(kvp => kvp.Key.Length)
						.ThenBy(kvp => kvp.Value.Source.Length);
				int shortestLength = orderedEnumerable.First().Key.Length;
				IEnumerable<KeyValuePair<string, Permutation>> bestPopulation =
					orderedEnumerable.TakeWhile(item => item.Key.Length == shortestLength);
				foreach (KeyValuePair<string, Permutation> pair in bestPopulation)
				{
					if (variantsPermuted.Add(pair.Key))
					{
						yield return pair;
					}
				}
			}

			foreach (string item in variantsFlooded
				.Except(variantsPermuted)
				.Where(str => str.Length == bestSolutionLength))
			{
				if (variantsPermuted.Add(item))
				{
					yield return
						new KeyValuePair<string, Permutation>(item,
						                                      new Permutation(item,
						                                                      new List<char>(item.ToCharArray()),
						                                                      "variant"));
				}
			}
		}

		private Permutation EvaluateEachIndividualInThePopulation(
			Grid grid,
			Dictionary<string, Permutation> population,
			IDictionary<string, Permutation> checkedPopulation,
			HashSet<string> variantsFlooded,
			Permutation bestSolution)
		{
			foreach (KeyValuePair<string, Permutation> pair in population.OrderBy(kvp => kvp.Key.Length))
			{
				if (variantsFlooded.Contains(pair.Key))
				{
					continue;
				}
				try
				{
					grid.Checkpoint();
					variantsFlooded.Add(pair.Key);
					ReplayStrategy strategy = new ReplayStrategy(pair.Value.Steps);
					Puzzle puzzle = new Puzzle(grid, puzzleConstants);
					Result result = puzzle.Flood(strategy, puzzleConstants.MaxFloods);
					List<char> solutionSteps = result.FillSteps;
					string key = solutionSteps.ConvertToString();
					if (!checkedPopulation.ContainsKey(key))
					{
						Permutation value = new Permutation(key, solutionSteps, pair.Value.Source + (pair.Key != key ? " flood" : ""));
						checkedPopulation.Add(key, value);
						if (solutionSteps.Count < bestSolution.Steps.Count)
						{
							bestSolution = value;
						}
					}
				}
				finally
				{
					grid.Undo();
				}
			}
			return bestSolution;
		}

		private Dictionary<string, Permutation> BuildInitialPopulation(Grid grid)
		{
			List<IFloodStrategy> strategies = new List<IFloodStrategy>
			                                  	{
			                                  		new FloodAdjacentColorThatHasTheMostDrySquaresRecurseToBreakTies(
			                                  			6,
			                                  			2,
			                                  			null,
			                                  			puzzleConstants),
			                                  		new FloodAdjacentColorThatHasTheMostDrySquaresPreferLargerShapes(),
			                                  		new FloodAdjacentColorThatHasTheMostDrySquaresPreferMoreColorsThenMostColors(),
			                                  		new FloodAdjacentColorThatHasTheMostDrySquaresPreferMoreColorsThenMostSquares(),
			                                  		new FloodAdjacentColorThatHasTheMostDryShapes(),
			                                  		new FloodAdjacentColorThatHasTheMostDrySquares(),
			                                  		new FloodAdjacentColorThatHasTheMostMoistSquares(),
			                                  		new FloodAdjacentColorThatHasTheMostDrySquaresPreferMoreBorderSquares()
			                                  	};

			Dictionary<string, Permutation> population = new Dictionary<string, Permutation>();

			for (int i = 0; i < strategies.Count; i++)
			{
				IFloodStrategy strategy = strategies[i];
				grid.Checkpoint();
				Puzzle puzzle = new Puzzle(grid, puzzleConstants);
				Result result = puzzle.Flood(strategy, puzzleConstants.MaxFloods);
				List<char> solutionSteps = result.FillSteps;
				string key = solutionSteps.ConvertToString();
				if (!population.ContainsKey(key))
				{
					population.Add(key, new Permutation(key, solutionSteps, "initial" + i));
				}
				grid.Undo();
			}
			return population;
		}

		private static void AddRemovalPermutations(IDictionary<string, Permutation> nextPopulation,
		                                           IEnumerable<KeyValuePair<string, Permutation>> population,
		                                           ICollection<string> variantsFlooded)
		{
			AddPermutations(nextPopulation, population, variantsFlooded, PermuteRemoval,
			                (oldLen, newLen, offset) => " x" + offset + (oldLen - newLen > 1 ? "D" : ""));
		}

		private static List<char> PermuteRemoval(IList<char> toPermute, int offset)
		{
			int end = offset;
			int start = offset + 1;

			bool validRemoval = toPermute.Skip(offset).GroupBy(color => color).Select(g => g.Count()).Any(x => x > 1);
			if (!validRemoval)
			{
				return null;
			}

			if (offset > 0)
			{
				if (toPermute[offset - 1] == toPermute[offset + 1])
				{
					start++;
				}
			}

			List<char> permutation = new List<char>(toPermute.Take(end));
			permutation.AddRange(toPermute.Skip(start).Take(toPermute.Count()));

			return permutation;
		}

		private static void AddSwapPermutations(IDictionary<string, Permutation> nextPopulation,
		                                        IEnumerable<KeyValuePair<string, Permutation>> population,
		                                        ICollection<string> variantsFlooded)
		{
			AddPermutations(nextPopulation, population, variantsFlooded, PermuteSwap,
			                (oldLen, newLen, offset) => " swap" + offset + (oldLen != newLen ? "D" : ""));
		}

		private static void AddPermutations(IDictionary<string, Permutation> nextPopulation,
		                                    IEnumerable<KeyValuePair<string, Permutation>> population,
		                                    ICollection<string> variantsFlooded,
		                                    Func<IList<char>, int, List<char>> permutor,
		                                    Func<int, int, int, string> getSource)
		{
			foreach (Permutation permutation in population.SelectMany(kvp => Permute(kvp.Value, permutor, getSource)))
			{
				if (variantsFlooded.Contains(permutation.Key) ||
				    nextPopulation.ContainsKey(permutation.Key))
				{
					continue;
				}

				nextPopulation.Add(permutation.Key, permutation);
			}
		}

		private static IEnumerable<Permutation> Permute(Permutation toPermute,
		                                                Func<IList<char>, int, List<char>> permute,
		                                                Func<int, int, int, string> getSource)
		{
			const int start = 0;
			int end = toPermute.Steps.Count - 1 - 1;
			for (int offset = start; offset < end; offset++)
			{
				List<char> steps = permute(toPermute.Steps, offset);
				if (steps == null)
				{
					continue;
				}
				string key = steps.ConvertToString();
				Permutation permutation = new Permutation(key, steps,
				                                          toPermute.Source + getSource(toPermute.Key.Length, key.Length, offset));

				yield return permutation;
			}
		}

		private static List<char> PermuteSwap(IList<char> toPermute, int offset)
		{
			int nextOffset = 1 + offset;
			bool validSwap = toPermute.Skip(offset).GroupBy(color => color).Select(g => g.Count()).Any(x => x > 1);
			if (!validSwap)
			{
				if (offset == 0 || toPermute[offset - 1] != toPermute[offset + 1])
				{
					return null;
				}
			}

			List<char> permutation = new List<char>(toPermute);
			char temp = permutation[offset];
			permutation[offset] = permutation[nextOffset];
			permutation[nextOffset] = temp;

			if (offset > 0)
			{
				if (permutation[offset] == permutation[offset - 1])
				{
					permutation.RemoveAt(offset);
				}
			}
			if (nextOffset + 1 < permutation.Count - 1)
			{
				if (permutation[nextOffset] == permutation[nextOffset + 1])
				{
					permutation.RemoveAt(nextOffset);
				}
			}
			return permutation;
		}

		public class Permutation
		{
			public string Key { get; private set; }
			public string Source { get; private set; }
			public List<char> Steps { get; private set; }

			public Permutation(string key, List<char> steps, string source)
			{
				Key = key;
				Steps = steps;
				Source = source;
			}
		}

		public class ReplayStrategy : IFloodStrategy
		{
			private readonly List<char> toReturn;
			private int offset;
			private int usedCount;

			public ReplayStrategy(List<char> toReturn)
			{
				this.toReturn = toReturn;
			}

			#region IFloodStrategy Members

			public Result GetNextToFlood(IEnumerable<Shape> moistShapes, Grid grid)
			{
				if (offset < toReturn.Count)
				{
					HashSet<char> adjacentColors = new HashSet<char>(moistShapes.Select(shape => shape.Color));
					while (offset < toReturn.Count &&
					       !adjacentColors.Contains(toReturn[offset]))
					{
						offset++;
					}

					if (offset < toReturn.Count)
					{
						usedCount++;
						return new Result(toReturn[offset], false);
					}
				}

				return
					new FloodAdjacentColorThatHasTheMostDrySquaresPreferLargerShapes().GetNextToFlood(
						moistShapes, grid);
			}

			#endregion
		}
	}
}